package com.dy.分类.二叉树._114二叉树展开为链表;

import com.dy.树.TreeNode;

/*
给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6
将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
 */

/**
 * 思路：前序遍历，就地：
 */
public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        //保存左右子树
        TreeNode left = root.left;
        TreeNode right = root.right;

        //将左子树变为前序遍历序列
        flatten(root.left);
        //右子树也前序遍历
        flatten(root.right);

        //让左面为空
        root.left = null;
        //将右面设置为left
        root.right = left;
        TreeNode p = left;
        while (p != null && p.right != null) {
            p = p.right;
        }
        if (p == null) {
            root.right = right;
        } else {
            p.right = right;
        }


    }
}